package com.xypower.link;

import java.util.HashMap;
//复制含有随机指针节点的链表
public class CopyListWithRandom {
    public static class  Node{
        public int value;
        public Node next;
        public Node rand;
        public Node (int data){
            this.value = data;
        }
    }
    //解法1  hashmap
    public static Node copyListWithRand1(Node head){
        HashMap<Node,Node> map = new HashMap<Node, Node>();
        Node cur = head;
        while (cur != null){
            map.put(cur,new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }

    //解法2 新链表与旧链表相连
    public static Node copyListWithRand2(Node head){
        if (head ==null){
            return null;
        }
        Node cur = head;
        Node next = null;
        //1 -> 2
        //1 -> 1` -> 2
        while (cur!=null){
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node curCopy = null;
        //copy`
        while (cur !=null){
            next = cur.next.next;
            curCopy =cur.next;
            curCopy.rand = cur.rand !=null?cur.rand.next:null;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        //split
        while (cur!=null){
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next!=null?next.next:null;
            cur = next;
        }
        return  res;
    }
}
